제2강에 오신 것을 환영합니다. 이 과정의 전반적인 목표를 설정한 후, 이제 알고리즘 설계의 기초가 되는 기본적인 자료구조자료구조인 배열과 연결 리스트에 깊이 들어가보겠습니다.
배열과 연결 리스트는 메모리 내에서 데이터를 조직하는 가장 기본적이고 핵심적인 방식으로, 연속된과 분산된저장 관리 방식 간의 근본적인 갈등을 나타냅니다.
정의:자료구조란 효율적인 접근과 수정을 가능하게 하기 위해 데이터를 조직하고 저장하기 위한 특수한 형식입니다.
- 배열은 요소를 연속된메모리 위치에 저장하여 요소 주소를 직접 계산할 수 있게 합니다.
- 연결 리스트는 요소를 분산된메모리 위치에 분산되어 저장되며, 명시적인 포인터만으로 연결됩니다.
- 배열 접근은 직접 인덱싱($O(1)$)이며, 반면 연결 리스트 접근은 순회($O(n)$)가 필요합니다.
- 배열에서 삽입/삭제는 요소를 이동해야 하므로 $O(n)$복잡도가 발생합니다.
- 연결 리스트에서는 삽입/삭제가 단지 포인터 재연결으로만 이루어지며, 위치 $i$를 알면 $O(1)$ 성능을 달성할 수 있습니다.
- 연결 리스트는 각 노드가 데이터와 `next` 포인터를 모두 저장해야 하므로 더 높은 공간 오버헤드를 초래합니다.
복잡도 비교
| 특징 | 배열 | 단일 연결 리스트 |
|---|---|---|
| 메모리 할당 | 연속적 (고정 블록 크기 $n$) | 분산적 (동적 포인터) |
| 접근 시간 | $O(1)$ | $O(n)$ |
| 삽입/삭제 | $O(n)$ | $O(1)$ (위치 $i$를 알고 있을 경우) |
| 공간 오버헤드 | 최소 (데이터만) | 높음 (데이터 + next포인터) |